Fenwick Tree
a.k.a. Binary Indexed Tree (BIT)
Operations
可換モノイド$ Mの列$ (a_1, a_2, \dots, a_n)を扱う．
空間計算量$ \Theta(n)
$ \mathtt{new}()
列の項がすべて$ Mの単位元である Fenwick Tree を作成する．
時間計算量$ \Theta(n)
$ \mathtt{build}(a_1, a_2, \dots, a_n)
与えられた列を表現する Fenwick Tree を作成する．
時間計算量$ \Theta(n)
$ \mathtt{point\_append}(i, x)
$ a_iに$ a_i \cdot xを代入する．
時間計算量$ \Omicron(\log n)
$ \mathtt{prefix\_fold}(r)
$ a_1 \cdot a_2 \cdot \dots \cdot a_rを計算する．
時間計算量$ \Omicron(\log n)
$ Mの任意の元に逆元が存在する (i.e.$ Mがアーベル群を成す) とき，さらに以下の操作ができる．
$ \mathtt{get}(i)( =$ \mathtt{fold}(i, i))
$ a_iを取得する．
時間計算量$ \Omicron(\log n)
$ \mathtt{set}(i, x) ( =$ \mathtt{point\_append}(i, \mathtt{get}(i)^{-1} \cdot x))
$ a_iに$ xを代入する．
時間計算量$ \Omicron(\log n)
$ \mathtt{fold}(l, r) ( =$ \mathtt{prefix\_fold}(l - 1)^{-1} \cdot \mathtt{prefix\_fold}(r) )
$ a_l \cdot a_{l+1} \cdot \dots \cdot a_rを計算する．
時間計算量$ \Omicron(\log n)
Summary
https://gyazo.com/7bd4539ead34fdcb938840bb0d116bd6
prefix からの区間をたかだか$ \log(n)個の交わらない区間に分割する
https://gyazo.com/8813b4c10e34998506c8346b2e7d2556
$ iに対応する区間の長さは$ iの lsb (least significant bit) と対応している
$ \mathtt{point\_append}
https://gyazo.com/f1a7a7bea571a6747a7a4b783765a05a
$ \mathtt{prefix\_fold}
https://gyazo.com/548b962c4b0207963d14c0a4640b3d9d
References
Notes
添字は 1-based で閉区間が適している
$ \mathtt{fold}(l, r)には自明な実装 ($ \mathtt{prefix\_fold}(l - 1)^{-1} \cdot \mathtt{prefix\_fold}(r)) の他に定数倍高速な実装が存在する
bit scan forward の実装は i & (~i + 1) が良い．あるいは，添字を符号付き整数で表現している場合は負数表現が 2 の補数であることを仮定して i & -i ともできる．
$ \Omicron(\log n)で列を二分探索できる
Implementations
Problems
+ いもす法